package sort;

import java.util.Arrays;

public class QuickSort {
    //快速排序：
    public static void main(String[] args) {
        int[] arr = {25,18};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr){
        //调用quick函数
        quick(arr,0, arr.length - 1);
    }
    //递归实现所有区间的递归，使得从left到right区间的元素变得有序
    public static void quick(int[] arr,int left,int right){
        if (right - left <= 0){
            return;
        }
//        int div = parttion(arr,left,right);
//        int div = parttion2(arr,left,right);
        int div = parttion3(arr,left,right);
        quick(arr,left,div);
        quick(arr,div + 1,right);
    }
    //1.使用Hoare找到基准
    //将数组划分为两个区间,以下标i作为分割，该下标元素左边区间小于该下标上的值，右边区间大于该下标上的值
    public static int parttion(int[] arr,int left,int right){
        int i = left;
        int pivot = arr[left];
        int j = right;
        while(i < j){
            while(i < j && arr[j] >= pivot){
                j--;
            }
            while (i < j && arr[i] <=pivot){
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,i,left);
        return i;
    }

    //2.使用挖坑法找到基准
    public static int parttion2(int[] arr,int left,int right){
        int i = left;
        int j = right;
        int pivot = arr[left];
        while(i < j){
            while (i < j && arr[j] >= pivot){
                j--;
            }
            arr[i] = arr[j];
            while (i < j && arr[i] <= pivot){
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        return i;
    }
    //3.使用前后指针找到基准
    public static int parttion3(int[] arr,int left,int right){
        int cur = left + 1;
        int prev = left;
        while (cur <= right){
            if (arr[cur] < arr[left] && arr[++prev] != arr[cur]){
                swap(arr,cur,prev);
            }
            cur++;
        }
        swap(arr,left,prev);
        return prev;
    }

    public static void swap(int[] arr,int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}